/*
 * 0084. 落单的数 III
 * 给出2*n + 2个的数字，除其中两个数字之外其他每个数字均出现两次，找到这两个数字。
 * https://www.lintcode.com/problem/single-number-iii/description
 * 
 * 样例
 * 给出 [1,2,2,3,4,4,5,3]，返回 1和5
 * 
 * 挑战
 * O(n)时间复杂度，O(1)的额外空间复杂度
 *  
 * 2018.06.22 @jeyming
 */
package single_number_iii_0084;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Single_number_iii_0084 {
	/*
	 * @param A: An integer array
	 * @return: An integer array
	 */
	public List<Integer> singleNumberIII(int[] A) {
		// write your code here
		List<Integer> list = new ArrayList<Integer>();
		if(A.length == 2) {
			list.add(A[0]);
			list.add(A[1]);
			return list;
		}
		else {
			Arrays.sort(A, 0, A.length);
			for(int i = 0; i < A.length - 1; ) {
				if(((i + 1) < A.length) && (A[i] == A[i + 1])) {
					i += 2;
				} else {
					list.add(A[i]);
					i += 1;
				}
				//    		if(A[i] != A[i + 1]) {
				//    			if(i == 0) {
				//    				list.add(A[i]);
				//    				i += 1;
				//    			} else if(i == A.length - 2){
				//    				list.add(A[i]);
				//    				list.add(A[i + 1]);
				//    				i += 2;
				//    			} else {
				//    				list.add(A[i + 1]);
				//    				i += 2;
				//    			}
				//    		} else {
				//    			i += 2;
				//    		}
			}
			return list;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
